package 二叉树层序遍历.N叉树的层序遍历;


import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    /*
    给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
    树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 利用层序遍历，关键是如何鉴定该层节点遍历结束
        if(root == null)
            return Collections.emptyList();
        List<List<Integer>> result = new ArrayList<>();
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        List<Integer> ans = new ArrayList<>();
        TreeNode p, last = root;
        queue.offer(root);
        while (!queue.isEmpty()) {
            p = queue.poll();
            ans.add(p.val);
            List<TreeNode> childrens = p.children;
            for (TreeNode child : p.children) {
                if(child != null)
                    queue.offer(child);
            }
            if( p == last ){
                result.add(ans);
                ans = new ArrayList<>();
                last = queue.peekLast();
            }
        }
        return result;
    }
}
